package ranking;

public class HeapSort{
	
	private static void buildHeap(int[]elements, int lastIndex){
		int lastParentIndex=(lastIndex-1)/2;//获得最后一个父节点,即最后一个非叶子节点
		//叶子节点数为lastIndex/2向上取整，因此最后一个非叶子节点为节点个数向下取整
		for(int i=lastParentIndex;i>=0;i--){
			int parent=elements[i];
			int leftChild=elements[i*2+1];//左节点肯定存在
			int rightChild=leftChild;
			if(i*2+2<=lastIndex){
				rightChild=elements[i*2+2];//右节点不一定存在
			}
			int maxIndex=leftChild<rightChild?i*2+2:i*2+1;
			if(parent<elements[maxIndex]){
				swap(elements,i,maxIndex);
			}
		}
	}
	
	private static void swap(int[]elements, int firstIndex,int secondIndex){
		int temp=elements[firstIndex];
		elements[firstIndex]=elements[secondIndex];
		elements[secondIndex]=temp;
	}
	
	public static void heapSort(int[]elements){
		for(int i=elements.length-1;i>0;i--){
			buildHeap(elements,i);//建堆
			swap(elements,0,i);//交换根节点和最后一个节点
		}
	}
	
	public static void main(String[]args){
		int[]a={23,42,27,42,93,687,34,67,89};
		heapSort(a);
		for(int i=0;i<a.length;i++){
			System.out.println(a[i]+",");
		}
	}
	
}